/*
Date:20210513 18:43PM
key:二维数组dp[i][j]表示消耗i个操作，能到数组第j个位置。
    那么即是左上 上 右上
*/
class Solution {
public:
    int numWays(int steps, int arrLen) 
    {
        int tmp=(pow(10,9) + 7);
        long**mat=new long*[steps+1];
        for(int i=0;i<steps+1;i++)
        {
            mat[i]=new long[arrLen];
        }
        mat[0][0]=1;
        for(int i=1;i<arrLen;i++)
        {
            mat[0][i]=0;
        }
        int maxLen = min(steps+1 / 2, arrLen );
        for(int i=1;i<steps+1;i++)
        {
            for(int j=0;j<maxLen;j++)
            {
                if(j-1<0)
                {
                    mat[i][j]=mat[i-1][j]+mat[i-1][j+1];
                    mat[i][j]%=tmp;
                    continue;
                }
                if(j+1>arrLen-1)
                {
                    mat[i][j]=mat[i-1][j]+mat[i-1][j-1];
                }
                else
                {
                    mat[i][j]=mat[i-1][j]+mat[i-1][j-1];
                    //mat[i][j]%=tmp;
                    mat[i][j]+=mat[i-1][j+1];
                }
                
                mat[i][j]%=tmp;
                //cout<<mat[i][j]<<" ";
            }
        }
        return mat[steps][0];
    }
};